package t_486

var (
	dp  [][]int
	dps [][]bool
)

func predictTheWinner(nums []int) bool {
	l := len(nums)
	// TODO 需要证明
	if l&1 == 0 {
		return true
	}

	dp = make([][]int, l)
	dps = make([][]bool, l)

	for i := 0; i < l; i++ {
		dp[i] = make([]int, l)
		dps[i] = make([]bool, l)
		dp[i][i] = nums[i]
		dps[i][i] = true
	}

	return get(nums, 0, l-1) >= 0
}

func get(nums []int, i, j int) int {
	if dps[i][j] {
		return dp[i][j]
	}

	dp[i][j] = max(nums[j]-get(nums, i, j-1), nums[i]-get(nums, i+1, j))
	dps[i][j] = true

	return dp[i][j]
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}
